package com.tgy.leetcode;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 *
 * https://leetcode-cn.com/problems/binary-search-tree-iterator/
 *
 */

class BSTIterator {

    private Deque<Integer> container;

    public BSTIterator(TreeNode root) {

        container = new LinkedList<>();

        TreeNode node = root;
        Stack<TreeNode> stack = new Stack<>();
        while (true) {

            while (node != null) {

                stack.push(node);
                node = node.left;
            }

            if (stack.isEmpty()) {

                break;
            }

            node = stack.pop();
            container.addLast(node.val);
            node = node.right;
        }
    }

    public int next() {
        return container.removeFirst();
    }

    public boolean hasNext() {
        return !container.isEmpty();
    }
}

public class _173_二叉搜索树迭代器 {

    public static void main(String[] args) {

    }
}
